GRAPHS.PAL[HAL,HE]7 - www.SailDart.org

perm filename GRAPHS.PAL[HAL,HE]7 blob sn#183690 filedate 1975-10-27 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00014 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	  Data structures, GSINIT
C00006 00003	  NXTTIM
C00007 00004	  INVLDT
C00008 00005	  CHANGE, CHNGER
C00014 00006	  ADDCHG
C00016 00007	  GETVAL, GETVR0
C00018 00008	  EVALND, EVLCLC
C00023 00009	  ADDCLC
C00025 00010	  MAKEGN, DELGN, DELGN1
C00032 00011	  RLLST1, RLLST2
C00034 00012	  GET2WD, GET3WD
C00035 00013	  W2SPC, W3SPC, MP2WD, MP3WD
C00037 00014	  Known Bugs
C00038 ENDMK
C⊗;
;  Data structures, GSINIT

.SBTTL Graph routines.
;Graph structure definitions
;RHT 9/74  RF 6/75

COMMENT ⊗  
This is the runtime's prime evil,
The murderous graph nodes and interlocks.
⊗

;GRAPH NODES		;Explicitly released, formed from large block store.
	II==0
	XX  NXTGN	;Links all graph nodes.  Points to next one.
	XX  PRVGN	;Previous link in that chain
	XX  INVMRK	;0 => valid, other => invalid
	XX  VALIDF	;a count which is incremented at every revaluation
	XX  GNVAL	;points at the value cell
	XX  GNDEPS	;list of dependent nodes.  (singly linked, absolute
			;  pointers, explicitly reclaimed)
	XX  GNCLCS	;list of calculator cells. (see format below)
	XX  GNCHGS	;list of change cells. (see format below)
	GNDSIZ == II/2	;Length of graph cell (in words)

;CELL LINKS
	II==0
	XX  DATUM	;Information
	XX  LINKF	;Forward link
	XX  LINKB	;Backward link, if any.  Singly linked chains don't use it.

;CALCULATOR CELL	;Explicitly released, formed from large block store.
	II==0
	XX  NXTCLC	;next calculator cell in chain
	XX  NEEDED	;list of needed nodes.  Each is a cell link whose datum
			;  is an absolute pointer and which is only forward linked.
	XX  CLCISB	;Points to interpreter status block to resolve addressing
	XX  CLCIPC	;the interpeter PC where the calculation starts
	CLCCSZ == II/2	;Size of calculator cell, in words

;CHANGER CELL		;Explicitly released, formed from large block store.
	II==0
	XX  NXTCHG	;next changer cell in chain
	XX  CHGISB	;Points to interpreter status block to resolve addressing
	XX  CHGIPC	;the interpeter PC where the calculation starts
	CHGCSZ == II/2	;Size of changer cell, in words

GNODES:  .BLKW 1	;head of chain of graph nodes.
TIME:	0		;used during evaluation of nodes
GNEVT:	.BLKW 1		;event for interlocking graph references

GSINIT:
;Initialize the graph structure to a null situation;
	EVMAK	;Make a new interlock event.
	MOV (SP),GNEVT;
	EVSIG 	;Give it one signal.
	CLR GNODES;
	CLR TIME;
	RTS PC	;Done
;  NXTTIM

COMMENT ⊗
	JSR	PC,NXTTIM
 	
Returns TIME←TIME+1 in R0.  If TIME goes negative then set all
positive mark cells to negative, then set time to 1. ⊗


NXTTIM:	INC	TIME		;TIME←TIME+1
	MOV	TIME,R0
	BGT	NXT.RT		;OK?
	MOV	GNODES,R0	;
	BEQ	NXTT.3		;DID WE HAVE ANY??
NXTT.1: TST	INVMRK(R0)	;YES
	BLE	NXTT.2		;WAS INVMRK POSITIVE
	NEG	INVMRK(R0)	;YES, NEGATE IT
NXTT.2:	MOV	NXTGN(R0),R0	;GO ON TO NEXT
	BNE	NXTT.1		;IF ANY
NXTT.3:	INC	R0		;R0←0+1
	MOV	R0,TIME		;TIME IS 1 AGAIN
NXT.RT:	RTS	PC

;  INVLDT

ROUTINE INVLDT,<INV.ND>
	MOV	INV.ND(RF),R0
	JSR	PC,INVLR0
	RTS	RF

INVLR0:	TST	INVMRK(R0)	;IS IT DEAD YET?
	BNE	INVL.R		;ALREADY INVALID??
INVL.1:	DEC	INVMRK(R0)	;NO, MAKE IT SO
	MOV	R2,-(SP)	;SAFE REGISTER
	MOV	GNDEPS(R0),R2	;DEPENDENTS
	BEQ	INVL.X		;IF ANY 
INVL.2:	MOV	DATUM(R2),R0	;GET A DEPENDENT
	JSR	PC,INVLR0	;AND INVALIDATE IT
	MOV	LINKF(R2),R2	;GO TO NEXT
	BNE	INVL.2		;IF ANY
INVL.X:	MOV	(SP)+,R2	;GET BACK SCRATCH REGISTER
INVL.R:	RTS	PC

;  CHANGE, CHNGER

COMMENT ⊗ Called by the outside world to put a new value, CHG.VNEW,
in the graph node CHG.ND.  Returns with CHG.ND in R0. ⊗

ROUTINE CHANGE,<CHG.ND,CHG.VNEW>
	MOV	R2,-(SP)	;Save R2
	MOV	R3,-(SP)	;Save R3
	MOV	CHG.ND(RF),R0	;R0 ← the target node.
	EVWAIT	GNEVT		;Wait until OK to enter critical code.
	JSR	PC,INVLR0	;invalidate it for the nonce
	MOV	CHG.ND(RF),R0	;R0 ← the target node
	MOV	GNVAL(R0),R2	;R2 ← old value
	MOV	CHG.VNEW(RF),GNVAL(R0) ;stow the new value
	MOV	GNCHGS(R0),R3	;R3 ← list of changers
	BEQ	CH.XXX		;if any
	EVSIG	GNEVT		;Leave the overall graph node critical region.
CH.1:	JSR	PC,CHNGER	;Call the next change routine
	MOV	NXTCHG(R3),R3	;R3 ← next changer
	BNE	CH.1
	EVWAIT	GNEVT		;Enter critical section again.
CH.XXX:	MOV	CHG.ND(RF),R0	;R0 ← the target node
	CLR	INVMRK(R0)	;Revalidate it
	INC	VALIDF(R0)	;Increment its validity count
	EVSIG	GNEVT		;Ok for others to enter critical code now.
	MOV	(SP)+,R3	;Restore R3
	MOV	(SP)+,R2	;Restore R2
	RTS	RF		;Return

CHNGER:
COMMENT ⊗ Calls the change routine indicated.  This is done by
instantiating a new interpreter to do the work.  It should terminate
the normal way, with a TERMINATE command.  R2 points to the old
value, and CHG.VNEW(RF) points to the "new value".  R3 points to the
changer cell.  These values are put into the new ISB.  GNODE
exclusion should be released before the call to CHNGER.  Recall that
a changer cell looks like this:
	XX  NXTCHG	;next changer cell in chain
	XX  CHGISB	;unformed and void
	XX  CHGISB	;Points to interpreter status block to resolve addressing
	XX  CHGIPC	;the interpeter PC where the calculation starts
⊗

	MOV R2,-(SP)	;Save R2
	MOV R3,-(SP)	;Save R3
	MOV R4,-(SP)	;Save R4

	;make a new interpreter to do the work
	MOV CHGISB(R3),R4	;R4 ← ISB we have to emulate
	MOV CHGIPC(R3),R0	;R0 ← IPC of new ISB
	EVMAK		;Stack a new event for communication with subsidiary
	MOV (SP),R1	;R1 ← copy of that event
	JSR PC,SPAWN	;R0 ← Process decriptor
	MOV PDBR4(R0),R4;R4 ← ISB of new interpreter
	MOV R2,OLDV(R4)	;Stow the "old value" pointer in environment.
	MOV CHG.VNEW(RF),NEWV(R4)	;Stow the "new value" pointer.
	FORK R0,#INTERP,#1	;Cause the new process to be started at high prio.

	;clean up after the interpreter
	EVWAIT 		;Wait for the completion event (still on stack)

	MOV (SP)+,R4	;Restore R4
	MOV (SP)+,R3	;Restore R3
	MOV (SP)+,R2	;Restore R2
	RTS PC		;Done
;  ADDCHG

ROUTINE ADDCHG,<ACH.ND,ACH.CHG>
COMMENT ⊗ ACH.ND is the target graph node, and ACH.CHG is a changer
cell all prepared except for the link to the other changers.  It is
necessary to perform this linking.  ⊗
	MOV	R2,-(SP)	;Save R2
	MOV	ACH.ND(RF),R2	;R2 ← LOC[target node]
	MOV	ACH.CHG(RF),R1	;R1 ← LOC[changer cell]
	EVWAIT	GNEVT		;Enter critical region for graph nodes
	MOV	GNCHGS(R2),NXTCHG(R1) ;Link new changer into list
	MOV	R1,GNCHGS(R2)	;
	EVSIG	GNEVT		;Leave critical region
	MOV	(SP)+,R2	;Restore R2
	RTS	R5		;Done
;  GETVAL, GETVR0

COMMENT ⊗ Called by the outside world.  Returns LOC[value(GTV.ND)] in
R0 and the VALIDF in R1, after having scrounged around to get a valid
value, if necessary and possible.  ⊗

ROUTINE GETVAL,<GTV.ND>
	MOV	GTV.ND(RF),R0
	JSR	PC,GETVR0
	RTS	RF

GETVR0:	TST	INVMRK(R0)	;Is the current value good?
	BEQ	GETV.R		;Yes
	EVWAIT	GNEVT		;No.  Enter critical region.
	MOV	R0,-(SP)	;Stack R0
	MOV	RF,-(SP)
	MOV	R0,-(SP)	;EVALNODE(GTV.ND,TIME←TIME+1)
	JSR	PC,NXTTIM	
	MOV	R0,-(SP)
	MOV	#MARK2,-(SP)
	MOV	SP,RF
	JSR	PC,EVALND		
	EVSIG	GNEVT		;Leave critical region
	MOV	(SP)+,R0	;R0 ← target node, now validated
GETV.R:	MOV	VALIDF(R0),R1	;Get the validity count
	MOV	GNVAL(R0),R0	;R0 ← value cell
	RTS	PC		;Done
;  EVALND, EVLCLC

COMMENT ⊗ EVALND is a recursive procedure, which is given EVL.ND, the
target node to evaluate, and EVL.T, the "time" of evaluation.  If
necessary, it calls itself at the same "time" to track down a chain
of related nodes.  GNEVT exclusion should be on at the time that
this routine is first called, and will remain on after the return. ⊗

ROUTINE EVALND,<EVL.ND,EVL.T>
	MOV	EVL.ND(RF),R0	;R0 ← target graph node
	MOV	INVMRK(R0),R1	;Is the node already valid?
	BEQ	EV.RTS		;Yes
	CMP	R1,EVL.T(RF)	;No.  Have we already looked at it this "time"?
	BEQ	EV.RTS		;Yes
	MOV	R2,-(SP)	;No.  Save R2
	MOV∪HfXZQM R∩wMCmJAHf~∀∪5∨,∪∂9π→π&!$`RYHd∩w$HA>AM%eghA
CYGk1Ci←d↓GKYX4∀∪¬D∪,]a10∩∩mSLAC9r~∃X]π→ h∪≠∨,%≥	∃λQ$d$Y$f∩m$fA>↓]KKI∃HAYSMhAM←HAiQSLAGCY
kYCi=d~∀∪	"∪X]≥∨⊗$∩wSL↓C]r~),]≥1 tAπ¬→_∪Yβ→≥λ0y	β)U~Q$f$Y-_9(Q%$|∩wYCYkCQJAiQ%fA]K∃H\~∀%≠∨,∪⊃β)+~!$fRYH`∩w$@A>AOICaPA9←IJA=LAiQ∀A]KK⊂~∀∪)M(∪∪≥Y≠%⊗QH`R∩w%fASh↓]←nAYCYSH|~∀∪¬9
∪,9≥1ε∩$w≥↑\A/SY0Aier↓iQJA9KqhA
CYGk1Ci←d4∀∪≠∨X∪→∪≥-Q$f$Y$f∩m3Kf\A$fA|A]KqPA]KK⊃KHAG∃YX~∀%¬≥
∪∃,]≥→@∩∩w∪_AC]r8~∃,9≥∨⊗t%πβ→_%-→π1εXy$H|∩wβ1XA]K∃IfACIJA[KP\@A$@A>AYCYkCQJAiQ∀AGCY
kYCi=d\~∀%≠∨,∪∃-_]≥⊂Q%R1$b∩wHbA>AQCeOKPA]←I∀~∀∪≠=,∪$`1∂≥-β0Q$bR$w'i←\ACoCdASif↓]KnAYCYkJ8~∀∪π1$∪∪≥Y≠%⊗QHbR∩w5CeVA%hACf↓mCYS⊂\~∀∪%≥ε∪-¬→∪	!$bR∩m∪]Ge∃[K]h↓SifAYCYSI%irA]U[EKd4∀∪¬$%,]1a0∩∩wIKCIr↓i↑AY∃CmJ~),]≥aεt∪≠=,∪≥1Qπ→εQHdRY$H∩w$d↓>A]KahAGC1GkYCQ←dAG∃YX~∀%¬≥
∪∃,]π→@∩∩wS_AC]r4∃,]a10t∪5∨,∩QM RVYHf∩w%∃gi←e∀A$f~(∪≠∨,$Q' R,Y$d∩m%Kgi=eJA$H~∃,9%)&t%%)&∪I∩∩w⊃←]J~(~∃π∨5≠≥(,AC
PAGC1GkYCQ←dAQ¬fABA→SKYH0Aπ→π%'∧XA]QSGP↓a←S]QfAi↑↓iQJ~)S]iKIaeKi∃dAgi¬ikfA	Y←GV↓←LASQfAIK→S]Si%←\\@↓)QSf↓G←]i¬S]fA∃]←kO ~∃S]→←e[CQS←\AQ↑AeKM←YmJ↓C]rAYCeSC	YJAe∃MKeK9GKfA%\AiQ∀AGCY
kYCi=d\~∃∃-→π→AGCY1fAiQ∀AS]i∃eaeKQKdAS8ABAgAKGSC0AoCrQiQe=kOPA∧Aπβ→0A∪≥)∃% R~)QCmS9NAMSIghAg∃hAk`↓BAag∃kI↑[%'∧AS8A$h\A/QK8AiQJ↓S]iKIaeKi∃d~∃e∃ike]LXAiQ∀AIKg%eKHAYCYkJ↓gQ←k1HAEJ↓S\A$@\@A¬GPAi%[J~∃∃-→π→ASfA
CYYK⊂XASh↓G←]gQekGiLABA]∃nAag∃kI↑[%'∧XAUgKfA%hA←]
JXAC9H~∃i!K\Ae∃YKCg∃fASh8@A)Q%fASf↓g←[K]QChA]CgiK→kXXA¬]HAG=kYHA	JAGY∃C]KH4∃k`\A-→
→εAe∃ike]LAiQJ↓mCYk∀AShA→←k]H↓S\A$@\@@,4∀~∃%=+)∪≥∀A-→
→εXy∃-ε]π1ε|~∀%≠∨,AHdXZQM R∩wMCmJAHd~∀∪5∨,A$LXZQ'@R∩w'¬mJA$L~∀∪≠=,A$h0ZQ' $∩w'CYJA$h4∀∪≠∨X@G∪'	&Y$`$w∂Kh↓BAag∃kI↑[%'∧~∀%∃'$AAεY∂)→%
∩m$`A>↓→∨π79KnA∪M¬:~∀%≠∨,AH`Y$h$w$hA|A→∨πm]KnA%'¬:~(∪≠∨,↓-ε]
→εQ%_RY$d$v~∀∪5∨,Aπ1π∪'∧!$dRYHb∩w$DA>A→=π7←Y⊂A∪'¬t~∀∪≠=,A≥XQ$bR1≥,QHhR∩w
←arA∃]mSe=][K]Qf~∀∪5∨,A→∃,Q$b$Y→,!$hR∩mπ←ar↓YKmK1f~∀∪5∨,Aπ1π∪!ε!$dRY%!εQ$PR∩w∪9SiSC1SuJAQQJA∪Aε~∀∪5∨,@G%≥')'hY$`∩l~∀∪∃M$A!ε1∂)
%∃
∩w$@A>A→=π7]K\AS]i∃eaeKQKdAgQCGW:4∀∪≠∨XA$`X4Q' R$w'Cm∀AiQJ↓giCG,AY←G¬iS←\4∀∪β	⊂@G∪≥M)'4YH`∩v~(∪≠∨,↓$`Y$L∩w$f↓>A→∨
7mKe≥JA←L↓]KnA%]iKeAeKiKHAgiC
W:~∀%πβ→_↓∪≥)I ∩w9iKdAQQJAS9iKeaIKiKd0A$`A|A→∨πm]KnAYCYkJ↓GKYYt~∀∪≠=,A$`1$d∩wHdA>A1∨π7]∃nAmC1kJAG∃YY:~(∪≠∨,↓$hY$@∩w%K1KCgJ↓iQJA%'∧~∀%∃'$AAεY%→→%
∩l~∀∪≠=,@Q'@RVY$@∩w%K1KCgJ↓iQJA%]iKeAeKiKHAgiC
V~∀∪)'$A!Y%→
I
∩v4∀∪≠∨XA$dYH`∩w%∃gkYh↓S\A$@\~∀∪5∨,@QM RVYHh∩w%∃gi←e∀A$h~(∪≠∨,Q' R,Y$f∩m%Kgi=eJA$L~∀∪≠=,@Q'@RVY$H∩w%KMi←eJ↓$d~∀%%)&∪I~∀_v@A¬		π→~∀~∃I∨+)∪9
Aβ	⊃π→εXqβ	λ]9λYβ	⊂]π→εx~∃π∨5≠≥(,Aβ	⊂]≥λA%fAiQ∀AiCe≥KhAOICaPA9←IJX↓C]HA¬	λ]π1εASf↓BAGC1GkYCQ←d~∃
KYXA¬YXAaIKaCe∃HAKq
KahA→←dAi!JAYS9VAi↑↓iQJA=iQKd↓GCYGUYCi←If\@A%h~∃SLA]KG∃ggCedAi↑AAKeM←IZAiQ%fAYS9WS]N↓C]HAQ↑AKgQCEYSMPAiQ∀AIKa∃]IK]
SKf~)Kqae∃ggKH↓ErAi!JA]K∃IKHA1Sgh\@,~∀%≠∨,∪HdXZQM R∩wMCmJAHd~∀∪5∨,∪$LXZQ'@R∩w'¬mJA$L~∀∪≠=,∪$h0ZQ' $∩w'CYJA$h4∀∪≠∨X∪β	λ9≥λQ%_RY$f$w$fA|A→∨πmiCeO∃hA]←⊃K:~∀%≠∨,∪¬	λ]π1εQ%$Y$b∩m$bA>↓→∨π7
CYGk1Ci←d↓GKYYt~∀∪Y/β∪(%∂≥-P∩∩w9iKdA
eSiS
CXAe∃OS←\4∀∪≠∨X∪∂≥π1π&Q$LRY≥1Qπ→εQHbR@w1S]VA9KnAG¬YGkY¬i←dA%]i↑A1Sgh~(∪≠∨,%$bY∂9π→π&!$fR∩l~∀∪≠=,∪≥∃	λQHbRY$H∩w$d↓>A→SMhA←L↓]KKI∃HAGK1Yf~∀%¬"∪¬π→ε]`∩∩w∪_AC]r4∃βπ→\bt∪)'$∪!Y∂(I/λ∩wH`A>A9KnAi]↑[o←IHAGK1XAM←HAIKa∃]IK]PAYSgP~∀∪≠=,∪$f1	β)+4Q$`R$w)Ce≥KhA]=IJASLA]←n↓IKaK9IK]h↓←LA]∃KIKH↓]←IJ4∀∪≠∨X∪	β)U~Q$d$Y$b∩m$bA>↓]Kqh↓]KKI∃HA]←⊃J~∀∪5∨,∪∂9	!&!$bRY1∪≥↔!$`R∩m→S]V↓]KnA⊃KaK]⊃K]hA%]i↑A1Sgh~(∪≠∨,%$`Y∂9	!&!$bR∩l~∀∪≠=,∪→∪9↔Q$HRY$d$w$dA|A]KqPA]KK⊃KHAG∃YX~∀%¬≥
∪¬π→ε\D∩∩wS_AC]r4∃βπ→]0t∪∃-'∪∞%∂≥-P∩∩w→∃CmJA
eSiS
CXAe∃OS←\4∀∪≠∨X∩Q' $VY$h$w%KgQ←eJAHh~∀∪5∨,∩QM RVYHf∩w%∃gi←e∀A$f~(∪≠∨,$Q' R,Y$d∩m%Kgi=eJA$H~∀∪%Q&∪$j$∩w	←9J~∀~(_v@A5β↔∂8XA	1∂≤XA⊃→∂≤D~∀~∃5β↔∂8t~∃π=≠≠≥P@,AπIKCiKLABAOICaPA9←IJX↓oSiP↓]↑AMISYYfQ]↑A
CYGk1Ci←eLX~∃kAICiKIfXAG!C]OKIfXAY=WgPX↓E←sI∃ZXAiMSEKY∀X@\\8RAKq
KahAQQChA%LA$`↓Sf~∃9←\[u∃e↑XAQQChA%fACgMk[KH↓i↑AE∀AiQJ↓mCYk∀AGKY0Aa←S9iKd\A)QJ↓]←IJ4∃oSY0AEJA5CeWK⊂ACfA%]mCY%HAk]1KgfAQQKeJ↓oCfAM←[JAYCYkJ↓OSmK8\@A)!J~∃gACGJA%fAiC-K\AMI←ZAY¬eOJA	Y←GV↓gi←e¬OJ\@↓)QJA9KnAOICaPA9←IJA%f~∃e∃ike]∃HAS\↓$`\@,~∀~(∪≠∨,↓$`XZ!' R∩m'CmJ↓$`~∀%≠∨,@
∂≥	'%4Y$`$v~∀∪)'$A!Y∂)
I
∩wH`A>A1∨π7]∃nAOe¬aPA]=IK:~(∪π→$↓∪≥-≠I⊗Q$`$∩w-C1SICi∀AiQJ↓]←IJ4∀∪≠∨X@Q' $VY∂≥Yβ_Q$@R∩w'QkMLA¬oCrAQQJAm¬YkJA
KYXAA←S]i∃d\~∀%¬≥
A5↔∂≤d$w/Cf↓iQKe∀A←]J|~∀∪≠=,@FZDY∪≥-5%⊗Q$@R∩w≥<\A∪]YCYSI¬iJAi!SfA]=IJ\~)≠↔∂≤Ht∪π→HA∂≥	∃!&Q$@R∩w5∃e↑A←QQKdA→SKYIL~∀∪π1$A∂≥
→π&QH`R∩v4∀∪π→HA∂≥π!∂&Q$@R∩v~(∪π→$↓≥1)∂8Q$`R$v~∀∪
→$A!I-∂≤QH`R∩v4∀∪π→HA-β→%	Q$@R∩v~(∪-/¬∪(A∂9-(∩mπeSi%GCXAMKGiS=\AQKIJ~∀∪5∨,A∂9∨	&1$b∩w1S]VAU`Ai↑↓←iQKHA]←I∃fAS\↓iQJA]←eYH8~∀∪¬∃"A≠↔≥≤b∩w%LAC]d~∀∪≠=,A$b1≥1)∂8Q$`Rl~∀∪≠=,A$`1!%-∂8Q$bRl~∃≠↔≥≤bt∪5∨,A$@Y∂≥∨⊃&∩v4∀∪-M∪∞A∂9-(∩m]HA=LAGe%iSGC0AgKGQS←\~(∪%)&↓!ε∩∩l~∀~∃⊃→∂≤h~∃π∨5≠≥(,A$`↓SfAi!JAY←
CiS←8A←LAQQJAOICaPA9←IJ\A	KgQekGi%←\ASLAB~∃YKerAQeSGWdAEkg%]Kgf8@AβY0AIKa∃]IK]QfA[kMhAMSIghAE∀AmCY%ICiK⊂XAiQ∃\~∃K¬GPA[UghAE∀AS]M=e[KH↓iQCh↓SifA
CYGk1Ci←d↓QCfA≥←]JA¬oCr\A)QSLA[KC9f~∃i!ChAi!JAa←%]iKd↓i↑Ai!JAmS
iSZA5kghA9←hAE∀AeK[=mKHA→e←ZAQQJ~∃∃]mSe=][K]PAk]i%XAiQ%fAoQ=YJA←AKeCi%←\ASLAMS]%gQKH8@A)Q∀AmCYUJAGK1X~∃[UghAE∀AeKG1CS[K⊂\@A)!SfASLAiCW∃\AGCIJA←L↓ErAe∃YsS]≤A←\AQQJAO¬eECO∀~∃G←1KGi←H\@A)!kfAOICaPA9←IKf↓[CrAMQCeJ↓mCYk∀AGKY1f\@AQQK\AQQJA]=IJ~∃%igKY_AGC\↓EJAk9YS]W∃HAMe=ZAiQ∀AGQC%\AC]⊂AeKiUe]KH↓i↑AMIKJAgQ←eCO∀\@,~(~∀∪≠=,A$d0ZQ' $∩∩w'¬mJA$H~∀∪≠=,A$f0ZQ' 		;Save R3
	MOV R0,R2		;R2 ← Graph node to delete
	EVWAIT GNEVT		;The whole procedure is critical.

	;Handle the dependents
	MOV GNDEPS(R2),R3	;R3 ← List of dependents
	BEQ DEL3		;if any
	JSR PC,NXTTIME		;R0 ← next "time"
	MOV R0,-(SP)		;Save "time"
DEL2:	MOV (SP),R0		;Validate all dependents with this "time".
	CALL EVALND,<DATUM(R3),R0>
	CALL DELGN1,<DATUM(R3),R2>	;Remove calculator from dependent
	MOV LINKF(R3),R3	;R3 ← next dependent
	BNE DEL2		;if any
	TST (SP)+		;clean off stack
	MOV GNDEPS(R2),R0	;R0 ← list of dependents
	JSR PC,RLLST1		;Release the storage in the dependents list.

	;Reclaim the calculator cells
DEL3:	MOV GNCLCS(R2),R3	;R3 ← First calculator cell
DEL4::	MOV R3,R0		;R0 ← current calculator cell
	BEQ DEL5		;If any
	MOV NXTCLC(R3),R3	;R3 ← next calculator cell
	JSR PC,RLFREE		;Release current one
	BR  DEL4		;Do the others

	;Reclaim the changer cells
DEL5:	MOV GNCHGS(R2),R3	;R3 ← First changer cell
DEL6::	MOV R3,R0		;R0 ← current changer cell
	BEQ DEL7		;If any
	MOV NXTCLC(R3),R3	;R3 ← next changer cell
	JSR PC,RLFREE		;Release current one
	BR  DEL6		;Do the others

	;Unlink this graph node
DEL7:	MOV NXTGN(R2),R1	;R1 ← forward link
	MOV PRVGN(R2),R0	;R0 ← backward link
	MOV R0,PRVGN(R1)	;
	MOV R1,NXTGN(R0)	;
	EVSIG GNEVT		;Leave critical region.

	MOV R2,R0		;R0 ← target graph node hulk
	JSR PC,RLFREE		;Release it.
	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS PC			;Done

ROUTINE DELGN1,<DLG.GN,DLG.GONE>;  

COMMENT ⊗ The graph node pointed to by DLG.GN must have all
calculators removed that depend on DLG.GONE, another graph node. 
Effort has already been made to validate DLG.GN, so no need to try it
again.  Just find all such calculators, and get rid of them.  It is
assumed that GNODE exclusion has been entered before this procedure
is called; it is still on when this procedure exits. ⊗
	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV DLG.GN(RF),R3	;R3 ← victim node
	MOV GNCLCS(R3),R2	;R2 ← list of calculators
	BEQ DELC1		;If any
	ADD #GNCLCS,R3		;R3 ← LOC[list of calculators]
DELC6:	MOV NEEDED(R2),R0	;R0 ← First needed cell
	BEQ DELC2		;If any
DELC5:	CMP DATUM(R0),DLG.GONE(RF)	;Is the departed mentioned in this will?
	BNE DELC3		;No
	MOV R2,R0		;R0 ← calculator cell to release
	MOV NXTCLC(R2),R2	;R2 ← next on list of calculators
	MOV R2,(R3)		;And patch up the previous link
	JSR PC,RLFREE		;Release the calculator cell
	TST R2			;Any more calculators?
	BNE DELC6		;Yes
	BR  DELC1		;No
DELC3:	MOV LINKF(R0),R0	;R0 ← next needed cell
	BNE DELC5		;If any
DELC2:	MOV R2,R3		;
	ADD #LINKF,R3		;R3 ← LOC[previous link field in calculator list]
	MOV NXTCLC(R3),R2	;R2 ← next calculator
	BNE DELC6		;If any
DELC1:	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS RF			;Done
;  RLLST1, RLLST2

RLLST1:
COMMENT ⊗ Free the storage used by the one-way list pointed to by R0.
Do not do anything to what is pointed to by DATUM(R0).  Just CDR down
LINKF. ⊗
	MOV R2,-(SP)	;Save R2
	MOV R0,R2	;R2 ← List header
	BEQ RLLS11	;If any
RLLS12:
	MOV LINKF(R2),R2;R2 ← next in list
    .IFNZ SMALLB
	MOV #W2SPC,R1	;
	JSR PC,FRESBK	;Release
    .IFF
	JSR PC,RLFREE	;Release
    .ENDC
	MOV R2,R0	;R0 ← next in list
	BNE RLLS12	;If any
RLLS11:	MOV (SP)+,R2	;Restore R2
	RTS PC		;Done

RLLST2:
COMMENT ⊗ Free the storage used by the two-way list pointed to by R0.
Do not do anything to what is pointed to by DATUM(R0).  Just CDR down
LINKF. ⊗
	MOV R2,-(SP)	;Save R2
	MOV R0,R2	;R2 ← List header
	BEQ RLLS21	;If any
RLLS22:
	MOV LINKF(R2),R2;R2 ← next in list
    .IFNZ SMALLB
	MOV #W3SPC,R1	;
	JSR PC,FRESBK	;Release
    .IFF
	JSR PC,RLFREE	;Release
    .ENDC
	MOV R2,R0	;R0 ← next in list
	BNE RLLS22	;If any
RLLS21:	MOV (SP)+,R2	;Restore R2
	RTS PC		;Done
;  GET2WD, GET3WD

COMMENT ⊗ Get a cell for pointers, either of the two-word or
three-word variety.  Note that JMP is used instead of JSR PC to
return to caller.  ⊗

GET2WD:	;Get a 2-word cell
    .IFNZ SMALLB
	MOV #W2SPC,R0	;
	JMP GETSBK	;Allocate from small blocks
    .IFF
	MOV #2,R0	;Number of words needed
	JMP GTFREE	;R0 ← LOC[new block]
    .ENDC

GET3WD:	;Get a 3-word cell
    .IFNZ SMALLB
	MOV #W3SPC,R0	;
	JMP GETSBK	;Allocate from small blocks
    .IFF
	MOV #3,R0	;Number of words needed
	JMP GTFREE	;R0 ← LOC[new block]
    .ENDC


;  W2SPC, W3SPC, MP2WD, MP3WD

;  Two and Three word cell space definitions and marking methods

W2SPC:	DEFSPC	W2ID,MP2WD,2,20,0,20,25
W3SPC:	DEFSPC	W3ID,MP3WD,3,20,0,20,25

;  At the moment, these are uncollectable spaces;

MP2WD:	TSTB	TAG(R0)
	BNE	MPRTS		;ALREADY DID THIS ONE
	JSR	PC,@2(RF)	;
	MOV	R2,-(SP)	;
	MOV	R0,R2		;SAVE RESULT OF ROUT
MPDLF:	MOV	DATUM(R2),R0	;DO DATUM
	JSR	PC,MARKR0	;
	MOV	R0,DATUM(R2)	;
	MOV	LINKF(R2),R0	;DO LINKF
	JSR	PC,MARKR0	;A LONG LIST WILL PDLOV (ALAS)
	MOV	R0,LINKF(R2)	; BUT WE DONT HAVE ANY LONG LISTS (I HOPE)
	MOV	R2,R0		;RETURN VALUE
	MOV	(SP)+,R2	;
MPRTS:	RTS	PC

MP3WD:	TSTB	TAG(R0)		;DID WE DO THIS
	BNE	MPRTS		;YES
	JSR	PC,@2(RF)	;
	MOV	R2,-(SP)
	MOV	R0,R2
	MOV	LINKB(R2),R0	;DO LINKB
	JSR	PC,MARKR0
	MOV	R0,LINKB(R2)	;
	BR	MPDLF		;GO DO DATUM & LINKF
;  Known Bugs

COMMENT ⊗ It is possible that while a graph node is changed, a
changer is invoked.  During its execution, some other process
modifies the change list for that node.  When the changer is done, it
may get lost in the changer cell list.  Graph node exclusion must be
turned off during execution of a changer, so that it can change other
cells.  Special changer exclusion causes deadlock in the case that
one changer triggers another.  

Certain variables, like YELLOW and BLUE, are not being initialized
to anything.
⊗